{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Autour du Laplacien\n", "\n", "On a déjà vu que la matrice d'adjacence d'un graphe permettait de construire des algorithmes efficaces pour résoudre certains problèmes, comme la recherche de chemins ou de composantes connexes.\n", "\n", "Ce n'est pas la seule matrice intéressante pour l'étude d'un graphe.\n", "Comme on l'a vu en cours, on peut définir une matrice que l'on appelle **la matrice laplacienne du graphe**.\n", "Cette matrice est la matrice suivante :\n", "$$L = D - A,$$\n", "où $A$ est la matrice d'adajcence du graphe, et $D$ une matrice diagonale contenant les degrés de chacun des sommets.\n", "\n", "Dans ce TP, on va essayer de comprendre ce qui motive la définition d'une telle matrice, et voir ce qu'on peut tirer de ces problèmes là." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import networkx as nx\n", "import numpy as np\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def liste_adjacence(G):\n", " adj = {}\n", " \n", " for sommet, adjacence in G.adjacency():\n", " adj[sommet] = adjacence.keys()\n", " \n", " return adj" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Dessiner Un Graphe\n", "### Quelques Exemples\n", "\n", "Jusqu'ici, on a utilisé la fonction `nx.draw` pour afficher des graphes.\n", "Si vous regardez bien, on a souvent appelé cette fonction avec un argument `pos`.\n", "\n", "Par exemple, on avait regardé ce graphe :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# génération d'un graphe\n", "G = nx.connected_caveman_graph(4,4)\n", "\n", "# calcul des positions des sommets du graphe\n", "pos = nx.spring_layout(G, seed=42)\n", "\n", "# affichage\n", "nx.draw(G, pos=pos, edgecolors=\"black\", node_color=\"pink\", with_labels=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Ici, on a appelé la fonction `nx.draw` avec l'argument `pos = nx.spring_layout(G, seed=42)`.\n", "On va voir comment cette fonction calcule les positions des points.\n", "\n", "Mais d'abord, regardons ce qu'il se passe si on donne une position aléatoire à chacun des poids :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# génération de positions aléatoires\n", "rng = np.random.default_rng(seed=42)\n", "pos_aleatoire = {u: rng.normal(size=2) for u in G.nodes()}\n", "\n", "# affichage\n", "nx.draw(G, pos=pos_aleatoire, edgecolors=\"black\", node_color=\"pink\", with_labels=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On comprend tout de suite beaucoup moins ce qu'il se passe dans ce graphe..." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Un Problème d'Optimisation\n", "\n", "Pour résoudre ce type de problèmes, une approche assez efficace consiste à utiliser des méthodes d'optimisations.\n", "Généralement, on définit une fonction qui dépend de nos données (ici de notre graphe), et d'un ensemble de paramètres.\n", "On cherche alors les paramètres qui minimisent cette fonction, ce qui, si on a bien défini la fonction, permet de trouver une solution à notre problème.\n", "\n", "Le problème est alors un problème de la forme :\n", "$$ \\min_{v \\in \\mathbb{R}^n} f(v; données).$$\n", "\n", "Si $f$ est différentiable, on peut calculer le gradient $\\nabla f$ de $f$.\n", "Ce gradient est intéressant, car il pointe dans la direction où $f$ augmente le plus vite.\n", "Ainsi, l'opposé du gradient $-\\nabla f$ pointe dans la direction où $f$ diminue le plus vite.\n", "\n", "La méthode la plus simple pour résoudre ce problème est la descente de gradient.\n", "On part d'une valeur des paramètres $v_0$, puis on avance dans la direction du gradient avec un pas $\\eta > 0$ :\n", "$$ v_{t+1} = v_t - \\eta \\nabla f(v_t).$$\n", "\n", "Par exemple, pour calculer la moyenne d'un ensemble de vecteurs $x_1, \\dots, x_K$, chacun ayant $n$ éléments, on a vu qu'on pouvait résoudre le problème :\n", "$$ \\min_{v \\in \\mathbb{R}^n} f(v) := \\frac {1}{2} \\sum_{i=1}^n \\|v - x_i\\|_2^2,$$\n", "où $v$ et $x_i$ sont des vecteurs de taille $d$.\n", "\n", "On peut calculer le gradient de $f$ :\n", "$$ \\nabla f(x) = \\sum_{i=1}^n w - x_i.$$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Exemple.**\n", "Les deux fonctions suivantes calculent la valeur de $f$ et de son gradient." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def f(v, x):\n", " # v est un réel\n", " # x est une liste de réels\n", " \n", " return 0.5 * np.sum(np.linalg.norm(v - x, axis=1) ** 2)\n", "\n", "def grad_f(v, x):\n", " return np.sum(v - x, axis=0)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Puis, on peut utiliser l'algorithme de descente de gradient suivant pour trouver la moyenne de nos valeurs :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def descente_gradient(x, f, grad, v0, nb_iter=5, eta=0.001):\n", " \n", " # on copie la valeur initiale pour éviter de la modifier sans faire exprès\n", " v = v0.copy()\n", " \n", " for t in range(nb_iter):\n", " \n", " # mise à jour avec le gradient\n", " v = v - eta * grad(v, x)\n", " \n", " return v" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# génération de données aléatoires\n", "rng = np.random.default_rng(seed=42)\n", "x = rng.random(size=(1000,2))\n", "\n", "# calcul de la moyenne par descent de gradient\n", "v = descente_gradient(x, f, grad_f, np.zeros(2), nb_iter=5, eta=0.001)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "print(\"Vraie moyenne : \", np.mean(x, axis=0))\n", "print(\"Moyenne calculée par notre algorithme : \", v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Modifiez la fonction `descent_gradient` pour garder en mémoire la valeur de la fonction $f$ à chaque itération.\n", "Affichez ensuite une courbe qui montre l'évolution de la fonction $f$ au cours des itérations." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def descente_gradient_mem(x, f, grad, v0, nb_iter=5, eta=0.001):\n", " # impélmentez la fonction" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# affichez la courbe des valeurs de f au fil des itérations" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Regardez ce qu'il se passe quand :\n", "* vous augmentez ou diminuez le learning rate $\\eta$ ;\n", "* vous changez le nombre d'itérations.\n", "\n", "Commentez." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# on pourra utiliser plt.subplots pour afficher plusieurs côte à côte :\n", "# fig, ax = plt.subplots(1, 2, figsize=(15, 5))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Calcul de la position des sommets du graphe\n", "\n", "Dans cette partie, on associe une valeur $v_s$ à chacun des points, où $v_s$ est un vecteur de longueur $2$, représentant la valeur des abscisses $x = v_s[0]$ et des ordonnées $y = v_s[1]$ de chacun des sommets du graphe.\n", "\n", "On a vu en cours que l'on pouvait trouver de bonnes valeurs pour $v_s$ en minimisant la fonction suivante :\n", "$$L(v; G) = \\frac 12 \\sum_{s \\in V} \\sum_{(s, s') \\in E} \\|v_s - v_{s'}\\|^2,$$\n", "en prenant soin de fixer la valeur de $v_s$ pour certains sommets.\n", "\n", "Le problème que l'on cherche à résoudre est donc maintenant un peu différent, car on cherche à calculer les valeurs de $x$ et $y$ pour chacun des points.\n", "On a donc $2n$ variables.\n", "\n", "Le coefficient $s$ du gradient de la fonction $L$ est :\n", "$$ \\nabla_{v_s} L(v; G) = 2 \\sum_{(s, s') \\in E} (v_s - v_{s'}),$$\n", "où l'on aura pris bien soin d'utiliser la valeur que l'on veut imposer à $v_{s'}$, et non un autre valeur !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Les fonctions suivantes permettent de calculer la valeur de $L$ et son gradient, avec certaines valeurs fixées." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def L(G, v, fixed_v):\n", " \n", " # on remplace les valeurs fixes de v par les valeurs fixes\n", " v = v.copy()\n", " for k in fixed_v:\n", " v[k] = fixed_v[k]\n", " \n", " # calcul de la matrice d'adjacence\n", " adjacency_matrix = nx.adjacency_matrix(G)\n", " \n", " # calcul de la matrice diagonale des degrés\n", " degree_matrix = np.diag(np.ravel(np.sum(adjacency_matrix, axis=1)))\n", " \n", " # calcul de la matrice laplacienne\n", " lap = degree_matrix - adjacency_matrix\n", " \n", " # renvoyer la valeur de la fonction\n", " return np.trace(0.5 * v.T @ lap @ v)\n", "\n", "def grad_L(G, v, fixed_v):\n", " \n", " # intiialisation\n", " adj = liste_adjacence(G)\n", " grad = np.zeros(v.shape)\n", " \n", " v = v.copy()\n", " for k in fixed_v:\n", " v[k] = fixed_v[k]\n", " \n", " # on calcule les coordonnées du gradient une par une\n", " for s in G.nodes():\n", " \n", " # si s est fixé, le gradient doit rester nul !\n", " if s not in fixed_v:\n", " \n", " # calcul...\n", " for s2 in adj[s]:\n", " grad[s] += 2 * (v[s] - v[s2])\n", " \n", " return grad" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Adaptez la fonction `descent_gradient` pour qu'elle prenne en entrée :\n", "* un graphe $G$ ;\n", "* la fonction $L$ et son gradient $grad\\_L$ ;\n", "* une matrice de taille $(n, 2)$ contenant les positions initiales de chacun des sommets (c'est $v_0$) ;\n", "* un dictionnaire $fixed\\_v$ dont les clés sont les sommets que l'on veut garder fixes, et qui associe à ces sommets leurs coordonnées (qui ne doivent donc pas bouger) ;\n", "* le learning rate $\\eta$ ;\n", "* le nombre d'itération $nb\\_iter$ ;\n", "\n", "et qu'elle renvoie les positions finales des sommets.\n", "\n", "*On fera bien attention à prendre en compte les valeurs fixes de $v$*." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "def descente_gradient_mat(G, f, grad, v0, fixed_v, nb_iter=5, eta=0.001):\n", " # implémentez la fonction" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.**\n", "Appelez votre fonction sur le graphe $G$, en plaçant le sommet $1$ en $(10, 0)$, le sommet $5$ en $(0, 10)$, le sommet $9$ en $(0, 0)$ et le sommet $13$ en $(10, 10)$. (Ces valeurs sont définies dans la variable `fixed_v`.)\n", "\n", "Affichez la valeur de la fonction $L$ au fur et à mesure, ainsi que \n", "\n", "Vous pourrez lancer l'algorithme avec un learning rate $eta = 0.1$ et pour $100$ itérations." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "# valeurs fixées de v\n", "fixed_v = {1: [10,0], 5: [0,10], 9: [0,0], , 13: [10,10], }\n", "\n", "# valeurs initiales de v\n", "v = np.zeros((len(G.nodes()), 2))\n", "\n", "\n", "### calculez la bonne valeur des positions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Affichez votre graphe avec les positions que vous avez calculées, en appelant la fonction `nx.draw` en donnant les valeurs que vous avez calculées à l'argument `pos`. Commentez." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# affichez le graphe avec les positions calculées à la question précédent" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remarque.** Pour comparer, voilà ce que l'on obtient avec la fonction de `networkx` qui procède de la même façon.\n", "Le résultat est différent car cette fonction ne fixe aucun point, mais cherche à laisser une distance minimale entre les sommets.\n", "Néanmoins le principe du calcul reste le même.\n", "\n", "On remarquera que \"spring\" signifie \"ressort\" en anglais, et que le nom de cette fonction vient du fait que l'on cherche à calculer les positions en considérant les arêtes comme des ressorts." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": true }, "outputs": [], "source": [ "pos = nx.spring_layout(G)\n", "nx.draw(G, pos=pos, with_labels=True, edgecolors=\"black\", node_color=\"pink\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Utilisation du spectre de la matrice laplacienne\n", "\n", "Dans cette partie, on va s'intéresser au spectre de la matrice laplacienne du graphe.\n", "\n", "**Question.** Commencez par définir une fonction qui prend en entrée un graphe et qui renvoie sa matrice laplacienne :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def matrice_laplace(G):\n", " \n", " # renvoyer la matrice laplacienne de G" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Affichez la matrice laplacienne du graphe `G` d'au dessus. Commentez les valeurs des coefficients de cette matrice." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "La fonction `np.linalg.eig` permet de calculer les valeurs propres d'une matrice, ainsi que les vecteurs propres associés.\n", "Elle renvoie un tuple dont le premier élément est la liste des valeurs propres de la matrice, et donc le second élément est une matrice dont les **colonnes** sont les vecteurs propres correspondants à ces valeurs propres." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Codez une fonction qui prend en entrée une matrice, puis qui utilise `np.linalg.eig` pour en calculer les valeurs propres, et qui les renvoie triés par ordre de valeur propre croissante." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def val_vec_propres(mat):\n", " # calculer et trier les valeurs propres" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Constatez que la plus petite valeur propre est bien nulle." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Pour afficher le graphe, on peut prendre les vecteurs propres correspondant aux deux plus petits valeurs propres non nulles. Le premier vecteur sera les abscisses des sommets, et le second leurs ordonnées.\n", "Affichez le graphe `G` de cette façon.\n", "\n", "Comparez ce que vous obtenez avec la fonction `nx.draw_spectral`, qui fait exactement les mêmes opérations." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# afficher G avec comme positions les valeurs des vecteurs propres appropriés" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# pour comparer :\n", "nx.draw_spectral(G, edgecolors=\"black\", node_color=\"pink\", with_labels=True)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remarque.** Quand le graphe n'est pas connexe, le nombre de valeurs propres nulles indique le nombre de composantes connexes.\n", "\n", "**Question.** Regardez les valeurs des valeurs propres obtenues pour le graphe suivant :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "G_non_connexe = nx.caveman_graph(3,3)\n", "nx.draw(G_non_connexe, edgecolors=\"black\", node_color=\"pink\", with_labels=True)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remarques.**\n", "La matrice Laplacienne d'un graphe est très utile en pratique.\n", "Ses vecteurs propres sont particulièrement intéressants, car, comme vous l'avez vu pour dessiner les graphes, elles contiennent des informations bien structurées sur le graphe.\n", "\n", "En particulier, on pourra s'en servir pour projeter des données en plus petite dimension, ce qui est particulièrement utile pour visualiser des données en dimension plus grande que 2.\n", "\n", "Cette matrice se retrouve aussi dans des algorithmes de clustering, et permet de capturer des informations sur la géométrie des clusters à retrouver.\n", "\n", "On va parler de tout ça dans les prochains cours." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }